package com.zjsru.oneDay202205;

import java.util.Arrays;

/**
 * @Author: likew
 * @Date: 2022/5/18
 * 乘法表中第k小的数
 *
 * 输入: m = 3, n = 3, k = 5
 * 输出: 3
 * 解释:
 * 乘法表:
 * 1	2	3
 * 2	4	6
 * 3	6	9
 *
 * 第5小的数字是 3 (1, 2, 2, 3, 3).
 *
 * 输入: m = 2, n = 3, k = 6
 * 输出: 6
 * 解释:
 * 乘法表:
 * 1	2	3
 * 2	4	6
 *
 * 第6小的数字是 6 (1, 2, 2, 3, 4, 6).
 *
 */
public class findKthNumber {
    /**
     *
     int m =9895, n = 28405, k = 100787757;
      当输入这组测试用例是 内存超出限制， 有改善空间
     * */
//    public int findKthNumber(int m, int n, int k) {
//        int high = m * n - 1, low = 0, ans = 0;
//        int[] nums = getNums(n,m);
//        Arrays.sort(nums);
//        while(low <= high){
//            int mid = (high - low)/2 + low;
//            if(nums[mid] == nums[k-1]){
//                ans = mid;
//                break;
//            }else if(nums[mid] > nums[k-1]){
//                high = mid - 1;
//            }else if(nums[mid] < nums[k-1]){
//                low = mid + 1;
//            }
//        }
//        return nums[ans];
//    }
//
//    private int[] getNums(int n, int m) {
//        int total = m * n;
//        int[] nums = new int[total];
//        while(total > 0){
//            for (int i = 1; i <= n; i++) {
//                for (int j = 1; j <= m; j++) {
//                    nums[total -1] = i * j;
//                    total--;
//                }
//            }
//        }
//        return nums;
//    }
    public int findKthNumber(int m, int n, int k) {
        int left = 1, right = m * n;
        while(left < right){
            int x = left + (right - left)/2;
            int count = x / n * n;
            for(int i = x/n + 1; i <= m; ++i){
                count += x/i;
            }
            if(count >= k){
                right = x;
            }else {
                left = x+1;
            }
        }
        return left;
    }
    
    
    public static void main(String[] args) {
        findKthNumber findKthNumber = new findKthNumber();
        int m =2, n = 3, k = 6;
        System.out.println(findKthNumber.findKthNumber(m, n, k));
    }
}
